import static java.lang.Math.abs;

public class Test {
    public static MySingleList.ListNode mergeTwoLists(MySingleList.ListNode list1, MySingleList.ListNode list2) {
        MySingleList.ListNode newHead = new MySingleList.ListNode(-1);
        MySingleList.ListNode newTail = newHead;

        while(list1 != null && list2 != null) {
            if(list1.val < list2.val) {
                newTail.next = list1;
                newTail = newTail.next;
                list1 = list1.next;
            }
            else {
                newTail.next = list2;
                newTail = newTail.next;
                list2 = list2.next;
            }
        }
        if(list1 != null) {
            newTail.next =list1;
        }
        if(list2 != null) {
            newTail.next =list2;
        }

        return newHead.next;
    }


    //相交链表
    public MySingleList.ListNode getIntersectionNode(MySingleList.ListNode headA, MySingleList.ListNode headB) {
        if(headA == null || headB == null)
            return null;
        MySingleList.ListNode plong = headA;
        MySingleList.ListNode pshort = headB;
        //分别求两个链表的长度
        int len1 = 0;
        int len2 = 0;
        //O(N)
        while(plong != null) {
            len1++;
            plong = plong.next;
        }
        while(pshort != null) {
            len2++;
            pshort = pshort.next;
        }
        plong = headA;
        pshort = headB;
        //2.求差值
        int len  = abs(len1 - len2);
        if(len < 0) {
            plong = headB;
            pshort = headA;
            //len = len2 - len1;
        }
        //3.让长的链表走差值步
        while(len != 0) {
            plong = plong.next;
            len--;
        }
        //4.一起走，直到相遇
        while(pshort != plong) {
            plong = plong.next;
            pshort = pshort.next;
        }
        return plong;
    }

    public static void main(String[] args) {
        MySingleList mySingleList1 = new MySingleList();
        mySingleList1.addLast(12);
        mySingleList1.addLast(23);
        mySingleList1.addLast(34);
        mySingleList1.addLast(45);

        MySingleList mySingleList2 = new MySingleList();
        mySingleList2.addLast(15);
        mySingleList2.addLast(20);
        mySingleList2.addLast(35);
        mySingleList2.addLast(30);

        MySingleList.ListNode ret = mergeTwoLists(mySingleList1.head,mySingleList2.head);
        mySingleList1.show2(ret);
    }


    public static void main1(String[] args) {
        MySingleList mySingleList = new MySingleList();
        //mySingleList.createList();
        //mySingleList.addFirst(-1);
//        mySingleList.addFirst(1);
//        mySingleList.addFirst(2);
//        mySingleList.addFirst(3);
        mySingleList.addLast(100);
        mySingleList.addLast(200);
        mySingleList.addLast(300);
        mySingleList.addLast(400);
        mySingleList.addLast(200);
        MySingleList.ListNode kval = mySingleList.findKthToTail(3);
        System.out.println(kval.val);
        mySingleList.show();
        MySingleList.ListNode ret = mySingleList.reverseList();
        mySingleList.show2(ret);
        mySingleList.show();
        //mySingleList.addIndex(0,11);
//        mySingleList.addIndex(2,22);
//        mySingleList.addIndex(7,33);
        System.out.println(mySingleList.size());
        System.out.println(mySingleList.contains(3));
        System.out.println(mySingleList.contains(0));
        mySingleList.remove(100);
        mySingleList.removeAllKey(200);
        mySingleList.show();
        mySingleList.clear();
        mySingleList.show();
        System.out.println();
    }
}
